from pathlib import Path
from queue import Queue
from typing import List, Iterator, Tuple, AnyStr

myDir = Path(r'I:\前端')


def walkBFS(root: Path):
    """广度优先遍历(层次遍历)N叉树-通过队列方式"""
    files = []
    queue = Queue()
    queue.put(root)
    while not queue.empty():
        path = queue.get()
        files.append(path)
        if path.is_dir():
            for p in path.iterdir():
                queue.put(p)
    return files


def walkDFS(root: Path):
    """深度优先遍历N叉树-递归方式"""
    files = []
    for path in root.iterdir():
        # files.append(path)  # 放前面为前序遍历
        if path.is_dir():
            files.extend(walkDFS(path))
        files.append(path)  # 放后面为后序遍历
    return files


def walkPreOrderDFS(root: Path):
    """深度优先前序遍历N叉树-通过栈方式"""
    files = []
    stack = [root]
    while stack:
        path = stack.pop()
        files.append(path)
        if path.is_dir():
            for p in reversed(list(path.iterdir())):
                stack.append(p)
    return files


def walkPostOrderDFS1(root: Path):
    """深度优先后序遍历N叉树-通过栈最后逆序输出方式

    后序遍历为先输出孩子节点再输出根节点，比如删除文件夹时要采用深度优先后序遍历，
    才能先删除文件夹内的文件再删除文件夹本身。
    """
    files = []
    stack = [root]
    while stack:
        path = stack.pop()
        files.append(path)
        if path.is_dir():
            for p in path.iterdir():
                stack.append(p)
    return files[::-1]


def walkPostOrderDFS2(root: Path):
    """深度优先后序遍历N叉树-通过第二个辅助栈方式"""
    files = []
    stack = [root]
    tmp = []  # 辅助栈
    while stack:
        path = stack.pop()
        tmp.append(path)
        if path.is_dir():
            for p in path.iterdir():
                stack.append(p)
    while tmp:
        files.append(tmp.pop())
    return files


def walk(top: Path, topdown=True) -> Iterator[Tuple[Path, List[AnyStr], List[AnyStr]]]:
    """模仿os.walk(top, topdown)的功能(python3.11版本已内置Path.walk方法)
    """
    dirs = []
    nondirs = []
    for path in top.iterdir():
        if path.is_dir():
            dirs.append(path.name)
        else:
            nondirs.append(path.name)
    
    if topdown:
        yield top, dirs, nondirs
    
    for dirname in dirs:
        yield from walk(top / dirname, topdown)
    
    if not topdown:
        yield top, dirs, nondirs


for i in walk(myDir,False):
    print(i)
